//
//  Problem23.swift
//  LeetCode - 23 合并K个排序链表
//
//  Created by 武侠 on 2020/7/13.
//  Copyright © 2020 zhulongiMac02. All rights reserved.
//

import UIKit

/*
 23 合并K个排序链表
 合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

 示例:

 输入:[
   1->4->5,
   1->3->4,
   2->6]
 输出: 1->1->2->3->4->4->5->6
 */


class Problem23: NSObject {
    func solution() {
        let nums = [[1, 4, 5], [1, 3, 4], [2, 6]]
        var lists:[ListNode?] = []
        for num in nums {
            if let node = createList(num) {
                lists.append(node)
            } else {
                lists.append(nil)
            }
        }
        
        if let node = mergeKLists1(lists) {
            printNode(node)
        }
    }
    
    // 方法1: 分而治之, 俩俩对比后, 合并
    func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
        if lists.count == 0 {
            return nil
        } else if lists.count == 1 {
            return lists[0]
        }
        return merge(lists, 0, lists.count - 1)
    }
    
    func merge(_ lists: [ListNode?], _ start: Int, _ end: Int ) -> ListNode? {
        if start == end {
            return lists[start]
        }
        if start > end {
            return nil
        }
        let mid = start + (end - start) / 2
        return mergeTwoLists(merge(lists, start, mid), merge(lists, mid + 1, end))
    }
    
    func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
        if list1 == nil {
            return list2
        }
        
        if list2 == nil {
            return list1
        }
        
        var slist1 = list1
        var slist2 = list2
        
        let head: ListNode = ListNode(0)
        var list: ListNode? = head
        while slist1 != nil, slist2 != nil {
            if slist1!.val < slist2!.val {
                list?.next = slist1
                slist1 = slist1?.next
            } else {
                list?.next = slist2
                slist2 = slist2?.next
            }
            
            list = list?.next
        }
        if slist1 != nil {
            list?.next = slist1
        } else if slist2 != nil {
            list?.next = slist2
        }
        
        return head.next
    }
    
    // 方法二: 每次比较每个队列的第一个, 取最小的值
    func mergeKLists1(_ lists: [ListNode?]) -> ListNode? {
        if lists.count == 0 {
            return nil
        } else if lists.count == 1 {
            return lists[0]
        }
        
        // 1: 创建一个数组, 存储的每个列表的第一个node
        var headList:[ListNode] = []
        for node in lists {
            if node != nil {
                headList.append(node!)
            }
        }
        
        
        let headNode = ListNode(0)
        var list: ListNode? = headNode
        while headList.count > 0 {
            //2: 遍历数组, 把最小的找到
            var minNode = headList[0]
            var l: Int = 0
            for i in 1..<headList.count {
                if headList[i].val < minNode.val {
                    minNode = headList[i]
                    l = i
                }
            }
            headList.remove(at: l)
            
            list?.next = minNode
            list = list?.next
            
            if let nextNode = minNode.next {
                headList.append(nextNode)
            }
            print(headList.count)
        }
        return headNode.next
    }
    
}
